package leetcode.base;

import common.TreeNode;

import java.util.*;

/**
 * Created on 2021/1/4 。
 *
 * @author wll 1978992154@qq.com
 */
public class TreeNodeBase {
    public List<Integer> tmp = new ArrayList<Integer>();

    /**
     * 二叉树前序遍历  非递归  DFS
     * 思路：先把头指针压栈 然后如果有左节点 就依次压栈 压到没有左子树了 就挨个出栈
     *
     * @param root 树的根节点
     * @return 前序遍历后的结果集列表
     */
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> tempList = new ArrayList<Integer>();
        Stack<TreeNode> q1 = new Stack<TreeNode>();
        if (root == null) {
            return tempList;
        }
        if (root != null) {
            q1.push(root);
        }
        while (!q1.empty()) {
            TreeNode t1 = q1.pop();
            if (t1.right != null) {
                q1.push(t1.right);
            }
            if (t1.left != null) {
                q1.push(t1.left);
            }
            tempList.add(t1.val);
        }
        return tempList;
    }

    /**
     * 显示二叉树 前序遍历 递归
     *
     * @param root 树的根节点
     */
    public static void displayTreeNode(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val);
        displayTreeNode(root.left);
        displayTreeNode(root.right);
    }


    /**
     * 二叉树层序遍历 自底向上 BFS
     * 思路：
     * 1.每一层的节点依次放入一个队列中
     * 2.根据放入的size确定需要从队列中取出多少个元素节点
     * 3.在取出的同时放入下一层的左右节点
     * 4.直到队列为空
     *
     * @param root 根节点
     * @return List结果集.
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        // 存放结果集的数组
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        // 创建一个临时队列
        Queue<TreeNode> tempQueue = new LinkedList<TreeNode>();
        if (root == null) {
            return result;
        }
        // 将根节点放入队列中
        tempQueue.offer(root);
        while (!tempQueue.isEmpty()) {
            List<Integer> temp = new ArrayList<Integer>();
            // 队列的size决定上一层节点的个数
            int size = tempQueue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = tempQueue.poll();
                temp.add(node.val);
                // 取出节点的同时,放入左右节点,便于下次循环取出来
                if (node.left != null) {
                    tempQueue.add(node.left);
                }
                if (node.right != null) {
                    tempQueue.add(node.right);
                }
            }
            result.add(temp);
        }
        // 最后翻转数组即可
        Collections.reverse(result);
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode root1 = new TreeNode(2);
        TreeNode root3 = new TreeNode(3);
        TreeNode root4 = new TreeNode(4);
        TreeNode root5 = new TreeNode(5);
        root.left = root1;
        root.right = root3;
        root1.left = root4;
        root4.left = root5;
        System.out.println(preorderTraversal(root));
        displayTreeNode(root);
        System.out.println(levelOrder(root));
    }
}
